package com.example.leetdemo.finash;

import java.util.*;

public class Solution1388 {


    public int minSetSize(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        int count = 0;
        List<int[]> list = new ArrayList<>();
        for(int key : map.keySet()) {
            list.add(new int[] { key, map.get(key)});
        }
        list.sort(Comparator.comparingInt(a -> -a[1]));
        for (int i = 0; i < list.size(); i++) {
            count += list.get(i)[1];
            if (count >= arr.length / 2 && arr.length % 2 == 0) {
                return i + 1;
            }
            if (count > arr.length / 2 && arr.length % 2 != 0) {
                return i + 1;
            }
        }
        return list.size();
    }


}
